11842 - Flatland/11842.2.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 #define DEBUG false
  28 #define dprintf DEBUG and printf
  29 #define dcout DEBUG and cout
  30
  31 inline int cmp(double x, double y = 0, double tol = 1e-9) {
  32     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  33 }
  34
  35 int Width, Height;
  36
  37 struct Vector {
  38     double x, y;
  39     Vector() {}
  40     Vector(double X, double Y) : x(X), y(Y) {}
  41     inline void normalize() {
  42         double length = sqrt(x * x + y * y);
  43         x /= length; y /= length;
  44     }
  45     bool operator < (const Vector &o) const {
  46         if (cmp(x, o.x) != 0) return cmp(x, o.x) < 0;
  47         return cmp(y, o.y) < 0;
  48     }
  49     bool operator == (const Vector &o) const {
  50         return (cmp(x, o.x) == 0 and
  51             cmp(y, o.y) == 0);
  52     }
  53 };
  54
  55 struct Person {
  56     double x, y;
  57     Vector d;
  58     string name;
  59
  60     Person(){}
  61     Person(double X, double Y, const Vector &D, string Name) : x(X), y(Y), d(D.x, D.y), name(Name) {}
  62
  63     bool operator < (const Person &o) { return name < o.name; }
  64
  65     double timeToFall() const;
  66
  67     friend ostream &operator<<(ostream &stream, const Person &p);
  68 };
  69
  70 double Person::timeToFall() const {
  71     double horizontal = cmp(this->d.x, 0) < 0 ? this->x / (-this->d.x) : (Width - this->x) / (this->d.x);
  72     double vertical   = cmp(this->d.y, 0) < 0 ? this->y / (-this->d.y) : (Height - this->y) / (this->d.y);
  73     return min(horizontal, vertical);
  74 }
  75
  76 ostream &operator<<(ostream &stream, const Person &p) {
  77     stream << p.name << " is at (" << p.x << ", " << p.y << ") moving in direction <" << p.d.x << ", " << p.d.y << "> (Might fall in " << p.timeToFall() << " seconds)";
  78     return stream;
  79 }
  80
  81 struct Death {
  82     string name;
  83     double time;
  84     Death(){}
  85     Death(const string &Name, double Time) : name(Name), time(Time) {}
  86     bool operator < (const Death &o) const {
  87         if (cmp(time, o.time) != 0) return cmp(time, o.time) < 0;
  88         return name < o.name;
  89     }
  90 };
  91
  92 struct Collision {
  93     double time;
  94     Vector point; // point of collision, if any
  95     vector<int> people; // the guy who fell or the two fellows that collided (contains indexes)
  96
  97     Collision(){}
  98     Collision(double Time) : time(Time) {}
  99     Collision(double Time, double x, double y, int personA, int personB) : time(Time), point(x, y) {
 100         people = vector<int>(2); people[0] = personA; people[1] = personB;
 101     }
 102
 103     bool operator < (const Collision &o) const {
 104         if (cmp(time, o.time) != 0) return cmp(time, o.time) < 0;
 105         return point < o.point;
 106     }
 107 };
 108
 109 double dot(const Vector &a, const Vector &b) {
 110     return a.x * b.x + a.y * b.y;
 111 }
 112
 113 bool outsideWorld(double x, double y) {
 114     if (cmp(x, 0) < 0) return true;
 115     if (cmp(x, Width) > 0) return true;
 116     if (cmp(y, 0) < 0) return true;
 117     if (cmp(y, Height) > 0) return true;
 118     return false;
 119 }
 120
 121 // Returns the time where person A and B would collide, or -1 if they won't.
 122 Collision collisionBetween(const Person &a, const int indexOfA, const Person &b, const int indexOfB) {
 123     if (Vector(a.x, a.y) == Vector(b.x, b.y)) {
 124         return Collision(-1.0); // They are on the same point, won't collide.
 125     }
 126
 127     double x0 = a.x, x1 = a.x + a.d.x;
 128     double y0 = a.y, y1 = a.y + a.d.y;
 129
 130     double x2 = b.x, x3 = b.x + b.d.x;
 131     double y2 = b.y, y3 = b.y + b.d.y;
 132
 133     double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
 134     double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
 135     double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
 136
 137     if (cmp(det, 0) == 0){
 138       //parallel
 139         if (cmp(t0, 0) == 0 || cmp(t1, 0) == 0) {
 140           // they lie on same line. But they might not collide (if they travel in the same direction)
 141             if (cmp(dot(a.d, b.d), 1) == 0) { // They travel in the same direction
 142                 return Collision(-1.0);
 143             }
 144             Vector pointOfCollision(x0 + (x2 - x0) / 2,
 145                 y0 + (y2 - y0) / 2);
 146
 147             double dist = hypot(x2 - x0, y2 - y0) / 2;
 148             if (cmp(x0 + dist * a.d.x, pointOfCollision.x) != 0 or cmp(y0 + dist * a.d.y, pointOfCollision.y) != 0 or
 149             cmp(x2 + dist * b.d.x, pointOfCollision.x) != 0 or cmp(y2 + dist * b.d.y, pointOfCollision.y) != 0) {
 150                 // they travel in opposite directions, but after traveling half the distance they haven't collided, so they'll never collide
 151                 return Collision(-1.0);
 152             }
 153             return Collision(dist, pointOfCollision.x, pointOfCollision.y, indexOfA, indexOfB); // they'll collide in half their distance because they travel in opposite directions
 154         }
 155         //just parallel, no intersection
 156         return Collision(-1.0);
 157     }
 158
 159     t0 /= det;
 160     t1 /= det;
 161
 162     if (cmp(t0, t1) == 0 and cmp(0.0, t0) <= 0 and cmp(0.0, t1) <= 0){
 163         double x = x0 + t0*(x1-x0);
 164         double y = y0 + t0*(y1-y0);
 165         if (outsideWorld(x, y)) return Collision(-1.0);
 166         return Collision(t0, x, y, indexOfA, indexOfB);
 167     }
 168     return Collision(-1.0);
 169 }
 170
 171 bool collidesWithSomeone(const vector< Person > &people, int i) {
 172     for (int j = 0; j < people.size(); ++j) {
 173         if (i == j) continue;
 174         Collision c = collisionBetween(people[i], i, people[j], j);
 175         dprintf("Colission between %s and %s:\n    Time = %lf, x=%lf, y=%lf\n", people[i].name.c_str(), people[j].name.c_str(), c.time, c.point.x, c.point.y);
 176         assert(cmp(c.time, 0) != 0); // if they collided, assert it wasn't at time 0
 177         if (cmp(c.time, 0) > 0) { // Bang!
 178             return true;
 179         }
 180     }
 181     return false;
 182 }
 183
 184
 185 // If there's someone who doesn't collide, it's added to the deaths vector and removed from the people vector.
 186 vector< Person > killOrBouncePeople(vector< Person > people, vector < Death > &deaths, double &elapsedTime) {
 187     for (int i = 0; i < people.size(); ++i) {
 188         if (!collidesWithSomeone(people, i)) {
 189             dcout << people[i].name << " doesn't collide with anyone. Killing!" << endl;
 190             deaths.push_back( Death(people[i].name, people[i].timeToFall()) );
 191             vector < Person > ans;
 192             for (int j = 0; j < people.size(); ++j) {
 193                 if (i != j) ans.push_back(people[j]);
 194             }
 195             return ans;
 196         }
 197     }
 198
 199     // Everybody collides here
 200     for (int i = 0; i < people.size(); ++i) assert(collidesWithSomeone(people, i));
 201
 202     // Now process collisions, by time.
 203     vector< Collision > collisions;
 204     for (int i = 0; i < people.size(); ++i) {
 205         for (int j = i + 1; j < people.size(); ++j) {
 206             Collision c = collisionBetween(people[i], i, people[j], j);
 207             if (cmp(c.time, 0) > 0) {
 208                 collisions.push_back( c );
 209             }
 210         }
 211     }
 212     assert(collisions.size() > 0);
 213     sort(collisions.begin(), collisions.end());
 214
 215     int i = 0, n = collisions.size();
 216     set<int> peopleWhoDiedInCollisions;
 217
 218     while (i < n and cmp(collisions[0].time, collisions[i].time) == 0) {
 219         int j = i;
 220         while (j < n and cmp(collisions[i].time, collisions[j].time) == 0 and collisions[i].point == collisions[j].point) {
 221             j++;
 222         }
 223         // collisions[i..j) have the same point and time)
 224         dprintf("Processing slice [i=%d, j=%d) of collisions:\n", i, j);
 225         for (int k = i; k < j; ++k) {
 226             dprintf("    Collision[k=%d]: time = %lf, x = %lf, y = %lf, people.size() = %d\n", k, collisions[k].time, collisions[k].point.x, collisions[k].point.y, (int)collisions[k].people.size());
 227         }
 228
 229         if (j - i == 1) { // two people
 230             // just swap their names
 231             int personA = collisions[i].people[0], personB = collisions[i].people[1];
 232             dprintf("Two people collided: %s and %s\n", people[personA].name.c_str(), people[personB].name.c_str());
 233             swap(people[personA].name, people[personB].name);
 234         } else { // more than two people
 235             for (int k = i; k < j; ++k) {
 236                 peopleWhoDiedInCollisions.insert( collisions[k].people.begin(), collisions[k].people.end()  );
 237             }
 238         }
 239
 240         i = j;
 241     }
 242
 243     vector< Person > newPeople;
 244     for (i = 0; i < people.size(); ++i) {
 245         if (peopleWhoDiedInCollisions.count(i) > 0) {
 246             deaths.push_back( Death(people[i].name, elapsedTime + collisions[0].time) );
 247         } else {
 248             Person p = people[i];
 249             p.x += collisions[0].time * p.d.x;
 250             p.y += collisions[0].time * p.d.y;
 251             newPeople.push_back( p );
 252         }
 253     }
 254     elapsedTime += collisions[0].time;
 255     dprintf("Elapsed time: %lf\n", elapsedTime);
 256     return newPeople;
 257 }
 258
 259 int main(){
 260     int Cases; cin >> Cases;
 261     while (Cases--) {
 262         dprintf("\n\n\n\nBegin case:\n");
 263         int n; cin >> n;
 264         cin >> Width >> Height;
 265
 266         vector<Person> people;
 267         for (int i = 0; i < n; ++i) {
 268             Person p;
 269             cin >> p.x >> p.y >> p.d.x >> p.d.y >> p.name;
 270             assert(cmp(floor(p.x), p.x) == 0 and cmp(floor(p.y), p.y) == 0); // people lie on integer coordinates
 271             p.d.x -= p.x; p.d.y -= p.y; p.d.normalize();
 272             people.push_back(p);
 273             dcout << p << endl;
 274         }
 275
 276         vector< Death > deaths;
 277         while (people.size() > 0) {
 278             double elapsedTime = 0;
 279             people = killOrBouncePeople(people, deaths, elapsedTime);
 280             dprintf("Remaining people:\n");
 281             for (int i = 0; i < people.size(); ++i) {
 282                 dcout << "       " << people[i] << endl;
 283             }
 284         }
 285         sort(deaths.begin(), deaths.end());
 286         for (int i = 0; i < deaths.size(); ++i) {
 287             dprintf("%s died at %lf\n", deaths[i].name.c_str(), deaths[i].time);
 288         }
 289         printf("%s\n", deaths.back().name.c_str());
 290     }
 291     return 0;
 292 }